/**
 * 
 */

/**
 * @author antonio081014
 * @since Nov 17, 2011, 8:08:21 AM
 */

public class MagicDiamonds {
	public long minimalTransfer(long n) {
		long count = 0;
		while (n > 0) {
			count++;
			n -= closestNonePrime(n);
		}
		return count;
	}

	public long closestNonePrime(long n) {
		for (long x = n; x >= 1; x--) {
			if (isPrime(x) == false)
				return x;
		}
		return -1;
	}

	public boolean isPrime(long n) {
		if (n == 2)
			return true;
		if (n <= 1)
			return false;
		if (n % 2 == 0)
			return false;
		for (long i = 3; i * i <= n; i += 2) {
			if (n % i == 0)
				return false;
		}
		return true;
	}

	// <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!
